package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author xxy
 * @create 2021 3 27 13:59
 */
public class HorseChessboard {
    private static int x;//列数
    private static int y;//行
    private static boolean visited[];
    private static boolean finished;//如果为true，则成功
    public static void main(String[] args) {
        x=8;
        y=8;
        int row=1;//从1 开始编号
        int column=1;//从1 开始
        int[][] chess=new int[x][y];
        visited=new boolean[x*y];
        long star = System.currentTimeMillis();
        horse(chess,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println(end-star);
        for(int[] link:chess){
            System.out.println(Arrays.toString(link));
        }
    }
    //可以走的集合
    public static ArrayList<Point> next(Point curPoint) {
        //创建ArrayList
        ArrayList <Point> ps=new ArrayList<>();
        //创建Point
        Point p1=new Point();
        //判断是否可以走这几个位置
       if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){
           ps.add(new Point(p1));
       }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<x&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<x&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<x&&(p1.y=curPoint.y+1)<y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<x&&(p1.y=curPoint.y+2)<y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+1)<y){
            ps.add(new Point(p1));
        }
        return ps;

    }
    public static  void horse(int[][] chessborad,int row,int column,int step){
        chessborad[row][column]=step;
        visited[row*x+column]=true;//标记已经走过
        //获取这个点可以走的下个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        //遍历ps
        //贪心，先排序
        sort(ps);
        while (!ps.isEmpty()){
            Point p =ps.remove(0);
            //判断是否访问过
            if(!visited[p.y*x+p.x]){
                //没有走过，继续走
                horse(chessborad,p.y,p.x,step+1);
            }
        }
        //判断是否走完
        if(step<x*y&&!finished){
            //没有走完
            chessborad[row][column]=0;
            //重新置为没有走过
            visited[row*x+column]=false;
        }else {
            finished=true;
        }
    }
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int count1=next(o1).size();
                int count2=next(o2).size();
                if(count1-count2<0){
                    return -1;
                }else  if(count1==count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}
